public class 课堂笔记 {
    public static int count=0;
    public static void main(String[] args) {
        //递归练习
        //代码示例1 按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)
//        print(1234);
        ////递归求 1 + 2 + 3 + ... + 10
//       int result = add(10);
//       System.out.println("result="+result);
        //代码示例3 写一个递归方法，输入一个非负整数，返回组成它的数字之和. 例如，输入 1729, 则应该返回
        //1+7+2+9，它的和是19
//        int result = sum(1729);
//        System.out.println("result=" + result);
          System.out.println(fib2(40));
//         // System.out.println(count);
    }

    public static int fib(int n){   // 执行结果102334155
                                    //count=39088169
        if(n==1||n==2){             // fib(3) 重复执行了 3 千万次
            return 1;
        }
        if(n==3){
            count++;
        }
        return fib(n-1)+fib(n-2);
    }
    //斐波那契数列问题改进(可以使用循环的方式来求斐波那契数列问题, 避免出现冗余运算)
    public static int fib2(int n){
        int last1=1;     //第前一个数
        int last2=1;     //第前两个数
        int current=0;   //当前数
        for(int i=3;i<=n;i++){    // 循环从 3 开始, 避免重复计算
            current=last1+last2;   // 当前数等于前两个数之和 ;如:current=1+1=2
            last2=last1;           // 前两个数等于前一个数.last1的值赋给last2
            last1=current;         // 前一个数等于当前数,current的值赋给last1
        }                          //此时::current=last1+last2=1+2=3,如此循环
        return current;   //循环结束后,返回current的值即为所求斐波那契数列第n项的值
    }

    public static int sum(int num){
        if(num>9){
            return num%10 + sum(num/10);
        }
        return num;
    }
    public static int add(int num){
        if(num == 1){
            return 1;
        }
        return num + add(num-1);
    }
    public static void print(int num){
        if(num>9){
            print(num/10);
        }
        System.out.print(num%10+" ");
    }


}
